package _剑指offer;

/**
 * @author Liu Huan
 */

public class _13_机器人的运动范围 {
    public static void main(String[] args) {
        System.out.println(movingCount(2, 3, 1));
    }
    
    public static int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return dfs(0, 0, m, n, k, visited);
    }
    
    private static int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
        if (i < 0 || i >= m || j < 0 || j >= n || (i % 10 + i / 10 + j % 10 + j / 10) > k) return 0;
        visited[i][j] = true;
        return dfs(i + 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited) + 1;
    }
    
}
